#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections
import cProfile

#二维数组转换为一维数组 [ [1,True][2,True]]  ->  [1,2]
def list2one(list):
    newlist = []
    for x in list:
        newlist.append(x[0])
    return newlist


#动态规划解决。


def pairToClass(pairMap):
    counter = 0
    result = []
    for k, v in pairMap.iteritems():
        if len(v)==1:
            if not v[0][1]:
                result.append([k,v[0][0]])
        else:
            for pair in v:
                if not pair[1]:
                    list = [k]
                    pair[1] = True
                    list.append(pair[0])
                    for pairCompare in v:
                        if pairCompare[0] != pair[0]:
                            #检验 是否已经与克隆类其他实例是克隆对。
                            flag = 0
                            for y in list:
                                counter = counter +1
                                z = min(pairCompare[0], y)
                                h = max(pairCompare[0], y)
                                if pairMap.get(z,-1) == -1 or (binary_search(list2one(pairMap.get(z)),h)==None):
                                    flag = 1
                                    break
                            if flag == 0:
                                for y in list:
                                    counter = counter + 1
                                    z = min(pairCompare[0], y)
                                    h = max(pairCompare[0], y)
                                    rindex = binary_search(list2one(pairMap.get(z)),h)
                                    pairMap.get(z)[rindex][1]= True
                                list.append(pairCompare[0])
                    result.append(list)
    print counter,'  t'
    return result


def easyPairToClass(pairMap):
    result = []
    def recur(key):
        value = pairMap.get(key,-1)
        if value != -1 and not value[0]:
            for member in value[1]:
                s.add(member)
                recur(member)
            value[0] = True

    for k,v in pairMap.iteritems():
        if not v[0]:
            s = set([])
            s.add(k)
            recur(k)
            result.append(sorted(list(s)))

    return result


def toDict(prilist):
    dict = collections.OrderedDict()
    for pair in prilist:
        dict[pair[0]] = dict.get(pair[0],[])
        dict[pair[0]].append([pair[1],False])
    for k,v in  dict.iteritems():
        v.sort()
    return dict


def toEasyDict(prilist):
    dict = collections.OrderedDict()
    for pair in prilist:
        dict[pair[0]] = dict.get(pair[0],[False,[]])
        dict[pair[0]][1].append(pair[1])
    for k,v in  dict.iteritems():
        v[1].sort()
    return dict


def binary_search(lst,value):
    low,high = 0 ,len(lst)-1
    while low <= high:
        mid = (low + high)/2
        if lst[mid] < value:
            low = mid + 1
        elif lst[mid] > value:
            high = mid - 1
        else:
            return mid
    return None



def classInsert():
    fhand =  open('C:\\Users\\huage\\CloneAnalyze\\ttokensclones_index_WITH_FILTER.txt')
   # for line in  fhand.readlines()[0:100]:
    prilist = []
    for line in fhand.readlines():
        block = line.split(',')
        begin = int(block[0])
        end = int(block[1])
        prilist.append([begin, end])

    return pairToClass(toDict(prilist))


if __name__=='__main__':
    prilist = (
    (11,12),
    (11,14),
    (11,13),
    (11,16),
    (11,15),
    (12,13),
    (12,14),
    (12,15),
    (13,15),
    (14,15),
    (14,17),
    )
    print prilist

    test = toEasyDict(prilist)
    print test


    print easyPairToClass(test)




    # print cmp(test[0],test[1])
    # print test
    # print test.get(11)
    # print sorted(test.get(11))
    # print test.get(11).sort()
    # print test.get(11)

    import time
    start = time.clock()
    zz = classInsert()
    print len(zz)
    print zz
    print (time.clock() -start)

